nclude <iostream>
#include <vector>
#include <string>

using namespace std;

namespace Close_Hash
{
    enum State { EMPTY, EXIST, DELETE };

    template<class K, class V>
    class HashTable
    {
        struct Elem
        {
            pair<K, V> _val;
            State _state;
        };

    public:
        HashTable(size_t capacity = 3)
            : _ht(capacity), _size(0), _totalSize(0)
        {
            for (size_t i = 0; i < capacity; ++i)
                _ht[i]._state = EMPTY;
        }

        // 插入
        bool Insert(const pair<K, V>& val)
        {
            //插入重复的直接跳过
            if (Find(val.first) < _ht.capacity())
                return false;
            //扩容
            CheckCapcity();

            //插入的值都是之前没有的
            size_t hashi = HashFunc(val.first);
            while (_ht[hashi]._state != EMPTY)
            {
                //线性探测
                hashi++;
                if (hashi == _ht.capacity())
                    hashi = 0;
            }
            _ht[hashi]._state = EXIST;
            _ht[hashi]._val = val;
            _size++;
            return true;
        }

        void CheckCapcity()
        {   //7 hy == 10size
            //负载因子大于70%扩容为二倍
            if (10 * _size >= 7 * _ht.capacity())
            {
                //用一个临时变量
                HashTable<K, V> newHT(_ht.capacity() * 2);
                for (size_t i = 0; i < _ht.capacity(); i++)
                {
                    if (_ht[i]._state == EXIST)
                    {
                        newHT.Insert(_ht[i]._val);
                    }
                }
                this->Swap(newHT);
            }
        }

        // 查找
        size_t Find(const K& key)
        {
            size_t findi = HashFunc(key);
            size_t pos = findi;
            while (_ht[findi]._state != EMPTY)
            {
                if (_ht[findi]._state == EXIST && _ht[findi]._val.first == key)
                    return findi;
                else
                    findi++;

                if (findi == _ht.capacity())
                    findi = 0;

                if (findi == pos)
                    return -1;
            }
            return -1;
        }

        // 删除
        bool Erase(const K& key)
        {
            //先看有没有
            size_t hashi = Find(key);
            if (hashi > _ht.capacity())
            {
                //说明没有
                return false;
            }
            //下来就说明有并且通过Find找到了
            _ht[hashi]._state = DELETE;
            _size--;
            return true;
        }

        size_t Size()const
        {
            return _size;
        }

        bool Empty() const
        {
            return _size == 0;
        }

        void Swap(HashTable<K, V>& ht)
        {
            swap(_size, ht._size);
            swap(_totalSize, ht._totalSize);
            _ht.swap(ht._ht);
        }

    private:
        size_t HashFunc(const K& key)
        {
            return key % _ht.capacity();
        }

    private:
        vector<Elem> _ht;
        size_t _size;
        size_t _totalSize;  // 哈希表中的所有元素：有效和已删除, 扩容时候要用到
    };
}

//int main()
//{
//    Close_Hash::HashTable<int, string> hs;
//    hs.Insert(make_pair(2, "123456"));
//    hs.Insert(make_pair(5, "666"));
//    hs.Insert(make_pair(7, "999"));
//    hs.Insert(make_pair(8, "333"));
//    hs.Insert(make_pair(12, "2222"));
//
//    cout << hs.Find(5) << endl;
//    cout << hs.Erase(5) << endl;
//    cout << hs.Erase(5) << endl;
//    cout<< hs.Find(5) << endl;
//    cout << hs.Size() << endl;
//    return 0;
//}
